#include "SinglyLinkedList.h"

// 打印单链表
void SListPrint(SListNode*phead)
{
	SListNode* cur = phead;
	while (cur!=NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
 
// 创建新的节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
 
// 在单链表尾部插入节点
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newndoe = BuySListNode(x);
 
	if (*pplist == NULL) 
	{
		*pplist = newndoe;
	}
	else
	{
		SListNode* cur = *pplist;
		while (cur->next!=NULL)
		{
			cur=cur->next;
		}
		cur->next = newndoe;
	}
	
}
 
// 在单链表头部插入节点
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}
 
// 删除单链表尾部节点
void SListPopBack(SListNode** pplist)
{
	assert(pplist && (*pplist));
	
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
 
// 删除单链表头部节点
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* temp = *pplist;	
	*pplist = (*pplist)->next;
	free(temp);
}
 
// 查找节点的值
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
 
// 在指定位置之前插入节点
void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pplist);
	assert(*pplist);
	assert(pos);
	if (*pplist == pos)
	{
		SListPushFront(pplist, x);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
 
// 在指定位置之后插入节点
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next=newnode;
}
 
// 删除指定位置的节点
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(*pplist);
	assert(pos);
	if (*pplist == pos)
	{
		SListPopFront(pplist);
	}
	else
	{
		SListNode* prev = *pplist;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
 
// 删除指定位置之后的节点
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* temp = pos->next;
	pos->next = pos->next->next;
	free(temp);
	temp = NULL;
}
 
// 销毁单链表
void SLTDestroy(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	while (cur)
	{
		SListNode* temp = cur->next;
		free(cur);
		cur = temp;
	}
	*pplist = NULL;
}

/*
无头单向非循环链表：
结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

1、为什么不在pos位置之前插入？
这是因为在单链表中，如果要在指定位置之前插入节点，需要知道指定位置之前的节点，而单链表的节点只能通过next指针找到下一个节点，无法直接找到前一个节点。因此，在单链表中，通常会选择在指定位置之后插入节点，或者通过其他方式重新组织链表来实现在指定位置之前插入节点的操作。

2、为什么不删除pos位置？
在单链表中，如果要删除指定位置的节点，需要知道指定位置之前的节点，以便修改前一个节点的next指针来跳过当前节点，从而实现删除操作。由于单链表的节点只能通过next指针找到下一个节点，无法直接找到前一个节点，因此删除指定位置的节点比较麻烦，需要遍历链表找到指定位置之前的节点。而删除指定位置之后的节点则相对容易，只需修改当前节点的next指针即可。因此，通常在单链表中会选择删除指定位置之后的节点，或者通过其他方式重新组织链表来实现删除指定位置的节点的操作。

*/

int main(int argc, char const *argv[])
{

    SListNode* plist= BuySListNode(2);
	SListPushBack(&plist, 3);
	SListPushFront(&plist, 1);
	SListPrint(plist);
	SListInsertAfter(SListFind(plist, 3), 4);
	SListPrint(plist);
	SListEraseAfter(SListFind(plist, 3));
	SListPrint(plist);
	SListPopBack(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SLTDestroy(&plist);
	SListPrint(plist);

    return 0;
}

 